package implementation.search;

public class InterpolateOrderedArray<K, V> extends AbstractOrderedArray<K, V> {


    public InterpolateOrderedArray() {
        amount = 0;
        array = new EntryI[50];
    }

    public InterpolateOrderedArray(int size) {
        amount = 0;
        array = new EntryI[size];
    }


    public int search(K key) {
        if (amount == 0) {
            return -1;
        }
        int low = 0;
        int high = amount - 1;

        int k = key.hashCode();
        int ku, kl, n, i;
        double l;
        while ((high - low) > 10) {
        //while (high > low) {
            n = high - low;
            kl = Math.abs(array[low].getKey().hashCode());
            ku = Math.abs(array[high].getKey().hashCode());

            if (k < kl || k > ku) {
                return -1;
            }

            l = low + ((double) (k - kl) / (double) (ku - kl)) * (n);
            i = (int) Math.round(l);
            int compare = key.hashCode() - (array[i].getKey()).hashCode();
            if (compare < 0) {
                high = i - 1;
            } else if (compare > 0) {
                low = i + 1;
            } else {
                return i;
            }
        }

        for (int j = low; j < high; j++) {
            if (k - (array[j].getKey()).hashCode() == 0) {
                return j;
            }
        }
        return -1;
    }
}

